从递归出发思考Google面试题另一种解法+24点游戏
作者：侯正平
一道 Google 的面试题公众号里已经发过，题目不再复述，这里只讲另一种分析过程。
根据题目所述，共有三种操作：
FILL(i):杯i装满水
DROP（i）:杯i倒空
POUR(i,j):杯i中的水倒入杯子j中，直至杯j满或杯i空
分析部分
这其中，POUR操作需要分两种情况（杯j满或杯i空），并且整个过程为FILL,DROP,POUR的不断循环，有重复性。因此，我们可以想方设法通过递归来实现这一过程。
很明显，递归的边界条件为：得到目标水容量。
代码部分
直接上代码，我们通过两个函数来实现这一过程。
fun1：预处理函数，根据容量大小标记杯子编号，分析无法操作的情况，然后调用fun2实现操作
def fun1(x,y,z): if x<z and y<z: print('目标水量大于两杯容量，无解') elif x>y: x,y = y,x if y%x==0 and z%x!=0: print('两杯容量为倍数关系，且与目标水量不为倍数关系，无解') else: print('将容量为%s的杯记为杯A'%x) print('将容量为%s的杯记为杯B'%y) fun2(x,y,z,y,z)fun2（x0,y0,x,y,z）:用来实现整个操作过程的递归函数，思路如下：
x0,y0:杯A和杯B当前的水量
x,y：杯A和杯B的容积
z：目标水量
为了方便理解，整个操作过程在函数中用文字表达，直接看函数和例子吧
def fun2(x0,y0,x,y,z): if y0 > x0: print('将杯B中的水倒入杯A直至杯A装满，然后倒掉杯A中的水，杯B中剩余水量为：%s'%(y0-x0)) if (y0-x0==z): print('成功！') else: fun2(x,y0-x0,x,y,z) if y0 < x0: if y0==z: print('成功！') else: print('将杯B中的水全部倒入杯A，然后将杯B装满，杯A中水量为%s'%y0) fun2(x0-y0,y,x,y,z)代码测试
A=14 B=5 C=3 fun1(A,B,C)可以看到，从递归的角度出发，问题就变得非常简单。
24点游戏
再举一个递归的例子，24点游戏
任给n个数，通过加减乘除括号运算计算24，返回所有可以得到24的计算方法。
注意这里不是4个数，是n个数！
问题分析
这样的问题，乍一看很难，但如果从递归的角度出发，就变得非常简单。
n个数的时候，每次任选两个数进行合并，合并方式可以为加减乘除，合并之后变为n-1个数，再次重复上述过程，直到只剩下一个数字。
如果这个数字是24，说明这种合并方法是我们需要的，如果不是，说明这种合并方法不是我们需要的，总结如下：
1. 若n=1，若此时值恰为24，输出
2. 若n >1,则从n个数中任取两个数x,y,计算x+y,x*y,x-y,x/y(y不为0时),y/x(x不为0时),y-x,从原数据中删去x,y共得到6组数，每组数的个数比原来少1，对这6组数，重复之前的步骤即可（若x,y中有0，则数的组数为5）
3. 让x,y遍历所有数，即可得到所有的情况
除此之外，唯一需要做的就是记录每次合并的方式。这通过字典结构可以很容易实现，代码和例子如下：（基于python2）
fun1:把输入的数字转为字典结构，然后调用fun
def fun1(nums): nums0 = dict(zip(map(str,nums),map(float,nums))) fun(nums0)fun:输出所有可以得到24的计算方法
def fun(nums): if len(nums) == 1: # 打印符合条件的计算方式 if nums.values()[0] == 24.0: print(nums.keys()[0]) # 长度大于2时,遍历所有的值，对六种情况进行递归 else: for i in range(len(nums)): for j in range(i): # 相加 nums1 = nums.copy() nums1['(' + str(nums.keys()[i]) + '+' + str(nums.keys()[j]) + ')'] = nums.values()[i] + nums.values()[j] nums1.pop(nums.keys()[i]) nums1.pop(nums.keys()[j]) fun(nums1) # 相减 nums1 = nums.copy() nums1['(' + str(nums.keys()[i]) + '-' + str(nums.keys()[j]) + ')'] = nums.values()[i] - nums.values()[j] nums1.pop(nums.keys()[i]) nums1.pop(nums.keys()[j]) fun(nums1) # 相乘 nums1 = nums.copy() nums1['(' + str(nums.keys()[i]) + '*' + str(nums.keys()[j]) + ')'] = nums.values()[i] * nums.values()[j] nums1.pop(nums.keys()[i]) nums1.pop(nums.keys()[j]) fun(nums1) # 相除(若分母为0，跳过运算) if nums.values()[j]!= 0: nums1 = nums.copy() nums1['(' + str(nums.keys()[i]) + '/' + str(nums.keys()[j]) + ')'] = nums.values()[i] / nums.values()[j] nums1.pop(nums.keys()[i]) nums1.pop(nums.keys()[j]) fun(nums1) # 换序相除(若分母为0，跳过运算) if nums.values()[i]!=0: nums1 = nums.copy() nums1['(' + str(nums.keys()[j]) + '/' + str(nums.keys()[i]) + ')'] = nums.values()[j] / nums.values()[i] nums1.pop(nums.keys()[i]) nums1.pop(nums.keys()[j]) fun(nums1) # 换序相减 nums1 = nums.copy() nums1['(' + str(nums.keys()[j]) + '-' + str(nums.keys()[i]) + ')'] = nums.values()[j] - nums.values()[i] nums1.pop(nums.keys()[i]) nums1.pop(nums.keys()[j]) fun(nums1)代码测试
nums = [1,2,3,4,5] fun1(nums)由此看到，从递归出发，一道难以下手的问题便迎刃而解。
关注公众号，“Python爱好者社区”，回复“爬虫”即可获取崔老师爬虫免费学习视频。
为大家提供与Python相关的最新技术和资讯。
长按指纹 > 识别图中二维码 > 添加关注